/*
 * MorrisPratt.cpp
 *
 *  Created on: 12-08-2013
 *      Author: Christian Charras - Thierry Lecroq
 *      http://www-igm.univ-mlv.fr/~lecroq/string/index.html
 */

#include "MorrisPratt.h"

#include "Config.h"

#include <stdio.h>

MorrisPratt::MorrisPratt()
{

}

MorrisPratt::~MorrisPratt()
{

}

std::string MorrisPratt::getName()
{
	return "Morris-Pratt";
}

int* MorrisPratt::preMp(std::string pattern)
{
	int patternSize = pattern.size();

	int* result = new int[patternSize + 1];


	int i = 0;
	int j = result[0] = -1;
	while (i < patternSize)
	{
		while (j > -1 && pattern[i] != pattern[j])
		{
			j = result[j];
		}
		result[++i] = ++j;
	}

	return result;
}


searchResult MorrisPratt::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	/* Preprocessing */
	int* mpNext = preMp(pattern);

	/* Searching */
	int i = 0, j = 0;
	while (j < textSize)
	{
		result.iterationsTaken++;

		while (i > -1 && pattern[i] != text[j])
		{
			i = mpNext[i];
		}

		i++;
		j++;

		if (i >= patternSize)
		{
			result.positionsFound.push_back(j - i);

			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}

			i = mpNext[i];
		}
	}

	return result;
}
